



		PE TABLA DE SAH - SOLUTIE
	       ---------------------------

( data de Dumitru Bogdan)

	La prima citire a textului, metoda de rezolvare cea mai indicata pare
a fi Branch&Bound. Insa aceasta metoda are deficientele ei: este destul de greu
de implementat, iar programul rezultat consuma multa memorie (nemaivorbind de
faptul ca este posibil sa nu se incadreze in timpul de executie).
	Daca insa estimam numarul total de configuratii posibile, remarcam ca
acesta este egal cu numarul de submultimi de 8 elemente ale unei multimi cu
16 elemente, adica C(16,8) = 12.870.
	Mai remarcam, de asemenea, ca fiecare configuratie poate fi codificata
printr-un numar, reprezentand echivalentul zecimal al numarul binar obtinut
prin liniarizarea ei. Algoritmul de rezolvare incepe sa se contureze: va fi o
"expandare", bazata pe ideea din algoritmul lui Lee. Vom folosi o structura de
date de tip coada, initializata cu starea initiala. La fiecare pas, vom adauga
toate configuratiile care se pot obtine din configuratia curenta si care nu au
fost obtinute inca. Astfel, fiecare configuratie este obtinuta intr-un numar
minim de pasi. Procesul se termina la obtinerea configuratiei finale (evident,
intotdeauna exista solutie - mai mult, se poate demonstra usor ca ea se obtine
in cel mult 24 de pasi).
	Pentru o mai buna intelegere a rezolvarii, se pot considera cele 12.870
de configuratii posibile ca fiind nodurile unui graf. Intre doua asemenea noduri
exista muchie de cost unitar daca ele reprezinta configuratii ce se pot obtine
una din alta printr-o singura mutare. Algoritmul implementeaza astfel o parcurgere
BF (in latime) a grafului, pornind de nodul ce reprezinta starea initiala si oprin-
du-se pe nivelul ce include nodul ce contine starea finala.